package com.zk.algorithm.array;

import com.zk.algorithm.FindMinimumInRotatedSortedArray;
import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.LeetCode;
import com.zk.algorithm.annotation.Medium;

/**
 * @author zk
 */
@Medium
@LeetCode("33")
public class SearchInRotatedSortedArray {

    public static void main(String[] args) {
        Utils.println(new SearchInRotatedSortedArray().search(new int[]{
                1
        }, 0));

        Utils.println(new SearchInRotatedSortedArray().search(new int[]{
                4,5,6,7,1,2,3
        }, 9));

        Utils.println(new SearchInRotatedSortedArray().search(new int[]{
                4,5,6,7,1,2,3
        }, 4));

        Utils.println(new SearchInRotatedSortedArray().search(new int[]{
                4,5,6,7,1,2,3
        }, 5));

        Utils.println(new SearchInRotatedSortedArray().search(new int[]{
                4,5,6,7,1,2,3
        }, 6));

        Utils.println(new SearchInRotatedSortedArray().search(new int[]{
                4,5,6,7,1,2,3
        }, 7));

        Utils.println(new SearchInRotatedSortedArray().search(new int[]{
                4,5,6,7,1,2,3
        }, 1));

        Utils.println(new SearchInRotatedSortedArray().search(new int[]{
                4,5,6,7,1,2,3
        }, 2));

        Utils.println(new SearchInRotatedSortedArray().search(new int[]{
                4,5,6,7,1,2,3
        }, 3));
    }

    /**
     * 1, 2, 3, 4, 5, 6, 7
     *         ||
     *         V
     * 4, 5, 6, 7, 1, 2, 3
     *
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        // ===========================
        // 寻找最小值
        // ===========================
        FindMinimumInRotatedSortedArray findMinimumInRotatedSortedArray = new FindMinimumInRotatedSortedArray();
        int minNumIndex = findMinimumInRotatedSortedArray.findMinIndex(nums);

        // ===========================
        // 搜索前半部分
        // ===========================
        int result = binarySearch(nums, 0, minNumIndex - 1, target);
        if (result == -1) {
            // ===========================
            // 搜索后半部分
            // ===========================
            result = binarySearch(nums, minNumIndex, nums.length - 1, target);
        }

        return result;
    }

    public int binarySearch(int[] nums, int begin, int end, int target) {
        if (begin < 0 || end < 0 || begin > end) {
            return -1;
        }

        while (begin <= end) {
            // ======================================================
            // + 优先级高于 >>
            //                 加括号              加括号
            //                   ↓                  ↓
            // int mid = begin + ((end - begin) >> 1);
            // ======================================================
            int mid = begin + ((end - begin) >> 1);
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                end = mid - 1;
            } else {
                begin = mid + 1;
            }
        }

        return -1;
    }

}
